NSF PAR Search | NSF Public Access Repository

VC-Dimension of Hyperplanes Over Finite Fields

https://doi.org/10.1007/s00373-025-02909-6

Ascoli, Ruben; Betti, Livia; Cheigh, Justin; Iosevich, Alex; Jeong, Ryan; Liu, Xuyan; McDonald, Brian; Milgrim, Wyatt; Miller, Steven_J; Romero_Acosta, Francisco; et al (March 2025, Graphs and Combinatorics)

Abstract Let$$\mathbb {F}_q^d$$

F_{q}^{d}

be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$

E \subseteq F_{q}^{d}

and a fixed nonzero$$t\in \mathbb {F}_q$$

t \in F_{q}

, let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$

H_{t} (E) = {h_{y} : y \in E}

, where$$h_y:E\rightarrow \{0,1\}$$

h_{y} : E \to {0, 1}

is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$

{x \in E : x \cdot y = t}

. Two of the authors, with Maxwell Sun, showed in the case$$d=3$$

d = 3

that if$$|E|\ge Cq^{\frac{11}{4}}$$

| E | \geq C q^{\frac{11}{4}}

andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$

H_{t} (E)

is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$

H_{t} (E)

isdwhenever$$E\subseteq \mathbb {F}_q^d$$

E \subseteq F_{q}^{d}

with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$

| E | \geq C_{d} q^{d - \frac{1}{d - 1}}

Search for: All records